The present invention relates to computer graphics and, more particularly, to improved methods and arrangements for use in rendering lighting and shadows in computer graphic simulations, such as, for example, interactive computer graphics simulations of multi-dimensional objects.
Computer generated graphics are becoming more popular in everyday computing especially given recent advances in affordable computer hardware and software. This trend is expected to continue in the foreseeable future. By way of example, interactive computer generated graphical images are becoming increasingly detailed and more realistic due to increased processing capabilities in personal computers (PCs). No where is this more evident than in the computer gaming arena, wherein virtual three-dimensional (3D) worlds are created in software and interactively explored by the computer""s user.
As with the real World, these virtual 3D worlds consist of a plurality of 3D objects. These 3D objects are typically modeled by one or more polygons. In the computer, depending upon the orientation of the scene being viewed, some of these polygons correspond to individual pixels that are displayed on the computer""s display screen. Within the computer, these pixels are represented by data that can be manipulated and stored in at least one data base. For example, once the arrangement of these 3D objects with respect to one another has been determined for a particular viewpoint, the rendered scene of the 3D world is projected onto a two-dimensional (2D) frame that can be displayed to the user. The frame is typically a data base that contains pixel color information with regard to the display screen.
A sense of motion within this virtual 3D world is provided by incrementally altering the arrangement of these 3D objects and quickly re-displaying the transformed frame. Typically, a frame rate of at least about twenty-five (25) frames-per-second (fps) is desired to convey a sense of motion.
Rendering such interactive 3D worlds, however, typically requires that millions of calculations be conducted between frames (i.e., in xe2x80x9creal timexe2x80x9d). Since there is a limit to the amount of processing that a computer can provide between frames, simplifications or other compromises often need to be made in modeling a 3D world. Additionally, advanced algorithms are implemented in either hardware and/or software to further streamline the processing of the resulting 3D scene and 2D images. Regardless of how the rendering computations are completed, the goal remains the same, namely, to provide a realistic, interactive virtual 3D world to the user.
One of the unfortunate compromises made in the past, has been in the area of lighting and, more particularly, in the area of rendering shadows cast by lighted 3D objects. Many shadow rendering processes have been considered to be too compute intensive for most lower-end computer applications, and as such shadow rendering is often ignored or otherwise greatly simplified. Several advanced and simplified shadow rendering algorithms and other graphical algorithms and techniques are described by James D. Foley, et al. in Computer Graphics: Principles and Practice, second edition, 1997 (ISBN 0-201-84840-6), published by Addison-Wesley Publishing Company, Inc. This text is expressly incorporated herein, by reference, in its entirety and for all purposes.
By way of a particular example, Foley et al. describe a promising two-pass object-precision shadow algorithm in Section 16.4.2 of the text. This two-pass shadow algorithm, developed by Atherton, Weiler and Greenberg, essentially determines which portions on a 3D object""s surfaces are visible from the perspective of a light source (i.e., from the light source""s view point). This requires converting the data for the 3D object, as represented in a data base, from a modeled world coordinate to a light source coordinate and then determining which portions of the various polygons are visible surfaces with respect to the light source, for example, using a hidden-surface removal algorithm. Since these visible portions are illuminated (i.e., lit) by the light source, the remaining portions (i.e., the hidden-surfaces) are darkened as being shaded from the light. The resulting data is then transformed back to modeling world coordinates and merged with the original object data base. This creates a viewpoint-independent merged data base that can be used to determine the shadows on the various 3D objects from any other viewpoint. This is the first step of the two-step shadow algorithm.
In the second step of the two-pass shadow algorithm, the data in the merged data base is then converted from the modeled world space to a corresponding screen (or camera) viewpoint. Then, a hidden-surface algorithm is used to determine which portions of the various polygons are visible surfaces with respect to the camera. These visible portions are identified as being visible to the camera and as being either not-darkened (i.e., lit) or darkened (i.e., in a shadow). A polygon scan-conversion algorithm is then used to render the resulting 2D image.
One of the drawbacks to this type of shadow algorithm is that unrealistic shadowing can occur in scenes having multiple light sources. Foley et al. for example, one page 747 of their text, teach that multiple light sources are handled by re-processing the merged data base for each new light source. Thus, for example, assume that a portion of a polygon which is visible from the camera viewpoint has been darkened because it is shaded from a first light source. This is information is recorded in the merged data base. Then, this merged data base is used as the starting point for a similar process for the second light source""s viewpoint determination. As part of this second light source""s viewpoint determination, additional darkening can occur to portions of the scene that are also shaded from the second light source. As a result, there is a potential for a portion of the scene to be darkened twice. In scenes having multiple light sources, including ambient light, this additive darkening of portions, and in particular, pixels, tends to reduce the realism of the shadowing effects and can lead to awkward shadowing cross-talk, wherein a shadow is made overly dark and has unrealistic transitions. This is especially true for applications using a xe2x80x9cstencil bufferxe2x80x9d technique for shadowing.
Additionally, when there are several light sources, for examples four or more, the transformation process associated with converting between the camera, world, and light viewpoints in support of this type of two pass algorithm can prove to be too burdensome, thereby inhibiting or otherwise diminishing the effectiveness of the resulting interactive real-time graphics.
Consequently, there is need for improved shadow rendering methods and arrangements. Preferably, the improved shadow rendering methods and arrangements support real time interactive graphics on conventional PCs and the like, and allow for multiple light sources to be modeled in a more efficient and realistic manner.
In accordance with certain aspects of the present invention, improved lighting and shadow rendering methods and arrangements are provided. These improved lighting and shadow rendering methods and arrangements can be implemented to support real time interactive graphics on conventional computers such as personal computers (PCs), computer gaming devices and the like. These improved methods and arrangements allow for multiple light sources to be modeled in a more efficient and realistic manner without becoming overly burdensome, or otherwise inhibiting or diminishing the effectiveness of the resulting interactive real time graphics.
For example, the above stated needs and others are met by a shadow rendering method for use in a computer system, in accordance with certain embodiments of the present invention. The method includes the steps of providing observer data of a simulated multi-dimensional scene and providing lighting data associated with a plurality of simulated light sources arranged to illuminate the scene. This lighting data includes light image data, for example. For each of the light sources, the method then includes the steps of comparing at least a portion of the observer data with at least a portion of the lighting data to determine if a modeled point within the scene is illuminated by the light source, and storing at least a portion of the light image data associated with the point and the light source in a light accumulation buffer. Once this is completed, the method includes the steps of combining at least a portion of the light accumulation buffer with the observer data, and displaying the resulting image data to a computer screen.
In accordance with certain further embodiments of the present invention, the observer data includes observed color data and observed depth data associated with a plurality of modeled polygons within the scene as rendered from an observer""s perspective. Thus, for example, the modeled polygons can be associated with a single pixel on the computer screen or a group of pixels, wherein the observed color data includes an observed red-green-blue value for the pixel(s) and the observed depth data includes an observed z-buffer value for the pixel(s). Similar data is provided for the lighting data, wherein, in certain embodiments, the lighting data includes source color data associated with at least one of the light sources and source depth data associated with the plurality of modeled polygons within the scene as rendered from a plurality of different light source""s perspectives.
In accordance with still further embodiments of the above method, at least a portion of the observed depth data is compared with at least a portion of the source depth data to determine if the modeled point is illuminated by the light source. This can include, for example, converting at least a portion of the observed depth data from the observer""s perspective to at least one of the plurality of different light source""s perspectives, before comparing the observed depth data with the source depth data. For fixed light sources and/or observer a precalculated matrix transformation look-up table can be used.
In accordance with other embodiments of the present invention, the above method can also be used to simulate dynamically changing light sources, interrupted light beams, reflected light beams, and/or projected light images, such as, for example, motion picture, video, animation, and computer graphics images. This can be accomplished, for example, by having at least a portion of the source color data being selectively controlled source color data, which can be changed over a period of time.
An arrangement that is configured to render shadows in a simulated multi-dimensional scene is also provided to meet the above stated needs and others, in accordance with certain further embodiments of the present invention. The arrangement includes a display screen configured to display image data, memory for storing data, such as, observer data, lighting data, light accumulation data, and frame data. At least one processor is coupled to the memory and the display screen and operatively configured to compare, for each of the plurality of light sources, observer data with lighting data to determine if a modeled point within the scene is illuminated by the light source and, if so, to store light image data in a light accumulation buffer, which can then be combined with observer data, and stored in the frame buffer for display via the display screen.
In accordance with still further embodiments of the present invention a method for simulating light falling on a modeled object in a computer generated multi-dimensional graphics simulation is provided. This method includes rendering a camera view of an object to produce a camera depth array and a corresponding camera image array, rendering at least one light view of the object to produce a light depth array and a corresponding light image array, and transforming camera depth data to the light view to produce a transformed camera array. The method further includes, for each data value therein, comparing the light depth array to the transformed camera array to determine if the data value in the light depth array is closer to the simulated light, and if so, adding a corresponding data value from the light image array to a light accumulation array, and then for each data value therein, multiplying the camera image array by a corresponding data value from the light accumulation array to produce a lighted camera image array.
The improved methods and arrangements of the present invention can be implemented in hardware and/or software. Thus, in accordance with certain embodiments of the present invention, a computer-readable medium is provided. A computer readable medium, by way of example, can include any tangible apparatus suitable for conveying or otherwise carrying at least one set of computer instructions. This can include a removable media associated with a computer system or a data communications link or network over which computer implemented instructions and/or data are carried, for example.
Thus, in accordance with certain embodiments of the present invention, such computer instructions are configured to cause a computer to operatively simulate light falling on a modeled object in a computer generated multi-dimensional graphics simulation by performing the following operations: 1) rendering an observer view; 2) rendering a source view; 3) transforming observed depth values to the source view; 4) modifying at least one image accumulation value with one of the observed image values if the corresponding transformed observer value is equal to a comparable one of the source depth values; 5) multiplying the one of the observed image values by the at least one image accumulation value to produce at least one pixel value; and 6) displaying the pixel value on a computer screen. In certain embodiments, following operation 4), operations 2) through 4) are repeated for each additional source.
In accordance with yet other embodiments of the present invention, there is provided a computer-readable medium carrying at least one set of computer instructions configured to cause at least one processor within a computer system to operatively render simulated shadows in a multi-dimensional simulated scene by performing the steps of providing observer data, providing lighting data, comparing observer data with lighting data to determine if a modeled point within the scene is illuminated by the light source, storing at least a portion of the light image data associated with the point and the light source in a light accumulation buffer, combining at least a portion of the light accumulation buffer with the observer data, and displaying resulting image data to a computer screen.